<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>WEEK 06</title>
</head>

<body>
    <script src="./week06.js"></script>

    <h1>第五、六周知识点总结</h1>
    <h2>贪心、分治、 回溯、 动态规划这四种算法思想又有什么区别和联系？</h2>
    <h3>
        贪心、回溯、 动态规划可以归为一类：三个算法解决问题的模型， 都可以抽象成多阶段决策最优解模型<br>

        分治单独可以作为一类：分治算法解决的问题尽管一部分也是最优解问题， 但是， 大部分都不能抽象成多阶段决策模型。<br>

        回溯：算法是个“万金油”。 基本上能用动态规划、 贪心解决的问题， 都可以用回溯算法解决。 回溯算法相当于穷举搜索。穷举所有的情况， 然后对比得到最优解。<br>

        动态规划解决的问题， 需要满足三个特征， 最优子结构、无后效性、重复子问题。<br>

        动态规划和分治的区别：在重复子问题这一点上，分治算法要求分割成的子问题，不能有重复子问题， 而动态规划正好相反， 动态规划之所以高效， 就是因为回溯算法实现中存在大量的重复子问题。<br>

        贪心法实际上是动态规划算法的一种特殊情况。通过局部最优的选择， 能产生全局的最优选择。
    </h3>
</body>

</html>